import java.util.LinkedList;

/**
 * ChainingHashTable.java
 * 
 * This class defines a hash table that uses external chaining to handle collisions
 * 
 * @author Ray DeCuir
 * @version 1.0
 *
 * @param <K> Generic Key type
 * @param <V> Generic Value type
 */

public class ChainingHashTable<K,V> implements IHashtable<K,V> {

	// instance variables to hold data about the chaining hash table
	private int entryCount, collisions, regrowCount, probeCount, regrowModifier;
	
	// the regrow / maximum loadfactor for the hash table
	private double loadfactor;
	
	// the backbone of the hash table implementation, 
	private LinkedList<Entry>[] table;
	
	
	/**
	 * Constructor for the ChainingHashTable object
	 * 
	 * @param initialSize The initial size of the hash table backing structure
	 * @param loadfactor The regrow factor for the hash table implementation
	 */
	@SuppressWarnings("unchecked")
	public ChainingHashTable(int initialSize, double loadfactor)
	{
		this.loadfactor = loadfactor;
		regrowModifier = 1;
		table = new LinkedList[ initialSize ]; 
		table = ( LinkedList<Entry>[] )table;
		this.collisions = 0;
		this.regrowCount = 0;
		this.probeCount = 0;
		this.entryCount = 0;
	}

	
	/**
	 * This method calculates and returns the rogrow factor / load factor of the hash table
	 * 
	 * @return The current loadfactor of the hash table
	 */
	@Override
	public double loadfactor() {
		int count = 0;
		for ( LinkedList<Entry> bucket : table)
		{
			if (bucket != null && bucket.size() != 0)
			{
				count++;
			}
		}
		return count / (double)table.length;
	}

	
	/**
	 * This function sets the regrow modifier of the hash table, the regrow multiplier is a constand 
	 * added to the size when the array is regrown
	 * 
	 * @param modifier The new regrow modifier
	 * 
	 */
	@Override
	public void setRegrowModifier(int modifier) {
		this.regrowModifier = modifier;
	}

	
	/**
	 * This function looks up the value stored in the hash table by a particular key.
	 * The method also returns this value
	 * 
	 * @param Key The key value to lookup
	 * 
	 * @return the Value associated with the key, or null if not found
	 */
	@Override
	public V lookup(K key) {
		int code = key.hashCode();
		int index = Math.abs(code)  % table.length;

		// nothing exists at this table location
		if (table[index] == null || table[index].size() == 0)
		{
			return null;
		}
		
		int count = 0;
		K value;
		while( count < table[index].size() )
		{
			value = table[index].get(count).key;
			if (value.equals(key)) 
			{
				//found
				probeCount++;
				return table[index].get(count).value;
			} 
			else 
			{
				//not at this index, try again on the linked list
				probeCount++;
				count++;
			}			
		}
		// nothing found, return null
		return null;
	}

	
	/**
	 * This method hashes a particular key and value pair and stores them in the hash table. This 
	 * table implementation uses linked lists for external chaining to handle collisions. 
	 * 
	 * @param Key The key value to hash
	 * @param Value THe value to store in the hash table 
	 * 
	 * @return 0 if the key has not been used to store data in the hashtable
	 * 			1 if the key has already been used
	 * 
	 */
	@Override
	public int insert(K key, V value) 
	{
		int temp = probeCount;
		if ( lookup(key) != null)
		{
			probeCount = temp;
			return 1;
		}
		else
		{
			int index = Math.abs(key.hashCode())  % table.length;
			if ( table[index] == null )
			{
				table[index] = new LinkedList<Entry>();
			}
			else if ( table[index].size() != 0)
			{
				collisions++;
			}
			entryCount++;
			table[index].addLast( new Entry(key, value) );
			if (loadfactor() > this.loadfactor) 
			{
				regrow();
				regrowCount++;
			}
			return 0;
		}
	}

	
	/**
	 * THis method regrows the backing table being used in the hash table
	 * All the values currently in the table are rehashed into the new table size
	 * 
	 * 
	 */
	@SuppressWarnings("unchecked")
	private void regrow() 
	{
		LinkedList<Entry>[] oldtable =  table;
	    table = new LinkedList[(oldtable.length * 2) + regrowModifier];
	    table = (LinkedList<Entry>[])table;
	    entryCount = 0;
		for (int i = 0; i < oldtable.length; i++) 
		{
			LinkedList<Entry> bucket = oldtable[i];
			int count = 0;
			while( bucket != null && count < bucket.size() )
			{
				insert( bucket.get(count).key, bucket.get(count).value );
				count++;
			}
		}	
	}

	
	/**
	 * This method removes the values from the hashtable that is associated with a specific key 
	 * 
	 * 
	 * @param Key The key of the value to be removed 
	 * 
	 * @return A boolean denoting if a value was removed from the hashtable, true if it has
	 */
	@Override
	public boolean remove(K key) 
	{
		int code = key.hashCode();
		int index = Math.abs(code)  % table.length;
		if (table[index] == null || table[index].size() == 0)
		{
			return false;
		}
		
		int count = 0;
		K tempKey;
		while( count < table[index].size() )
		{
			tempKey = table[index].get(count).key;
			if (tempKey.equals(key)) 
			{
				table[index].remove(count);
				entryCount--;
				return true;
			} 
			else 
			{
				count++;
			}			
		}
		return false;
	}

	
	/**
	 * 
	 * Method that returns a boolean denoting if a hashtable contains any values 
	 * 
	 * @return A boolean denoting if the table is empty or not
	 */
	@Override
	public boolean isEmpty() {
		return entryCount == 0;
	}

	
	/**
	 * Gets the current number of elements stored in the hash table
	 * 
	 * @return The number of elements stored in the hash table
	 */
	@Override
	public int size() {
		return entryCount;
	}

	/**
	 * This method returns the number of collisions that have happened in the hash table implementation 
	 * 
	 * @return The number of collisions currently recorded in the hash table
	 */
	@Override
	public int collisions() {
		return collisions;
	}

	/**
	 * Gets the number of times the hashtable has been regrown
	 * 
	 * @return The number of times the hash table has been regrown
	 */
	@Override
	public int regrowCount() {
		return regrowCount;
	}

	
	/**
	 * Gets the number of checks needed to insert elements into the hash table, called probes
	 * 
	 * @ return The number of probes used to insert elements in the hashtable
	 */
	@Override
	public int probeCount() {
		return probeCount;
	}
	
	
	/**
	 * Private class implementation that pairs Keys and Values into a single object
	 * 
	 * @author Ray DeCuir
	 * @version 1.0
	 *
	 */
	private class Entry
	{
		// The key and value of the information to be stored
		K key;
		V value;
		
		/**
		 * Constructor for the internal Entry class that pairs keys and values
		 * 
		 * @param key The key associated with the value
		 * @param value The value associated with a particular key
		 */
		public Entry(K key, V value)
		{
			this.key = key;
			this.value = value;
		}
	}
}
